/*
 * meituan.com Inc.
 * Copyright (c) 2010-2018 All Rights Reserved.
 */
package item27;

import org.junit.Assert;
import org.junit.Test;

/**
 * <p>
 *
 * </p>
 * @author LvJing
 * @version $Id:Mirror.java v1.0 2018/8/5 上午12:11 LvJing Exp $
 */
public class Mirror {

    /**
     * 面试题27：操作给定的二叉树，将其变换为源二叉树的镜像。
     * 二叉树的镜像定义：源二叉树
     *     	    8
     *     	   /  \
     *     	  6   10
     *     	 / \  / \
     *     	5  7 9 11
     *     	镜像二叉树
     *     	    8
     *     	   /  \
     *     	  10   6
     *     	 / \  / \
     *     	11 9 7  5
     *
     * 思路：典型的二叉树里递归应用，上来就是把根节点的左右子树交换，再以左节点为根节点，递归进行重复操作，右节点也是一样的。
     * 一般对于树的操作都是跟递归相关，遇到类似的题可以往这上面靠。
     */
    public class Solution {
        public void Mirror(TreeNode root) {
            if (root == null) {
                return;
            }

            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;

            if (root.left != null)
                Mirror(root.left);
            if (root.right != null)
                Mirror(root.right);
        }
    }

    public class TreeNode {
        int      val   = 0;
        TreeNode left  = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;

            TreeNode treeNode = (TreeNode) o;

            if (val != treeNode.val)
                return false;
            if (left != null ? !left.equals(treeNode.left) : treeNode.left != null)
                return false;
            return right != null ? right.equals(treeNode.right) : treeNode.right == null;
        }

        @Override
        public int hashCode() {
            int result = val;
            result = 31 * result + (left != null ? left.hashCode() : 0);
            result = 31 * result + (right != null ? right.hashCode() : 0);
            return result;
        }
    }

    @Test
    public void test01() {
        Solution solution = new Solution();
        TreeNode root = new TreeNode(8,
                new TreeNode(6, new TreeNode(5), new TreeNode(7)),
                new TreeNode(10, new TreeNode(9), new TreeNode(11)));

        solution.Mirror(root);

        TreeNode expect = new TreeNode(8,
                new TreeNode(10, new TreeNode(11), new TreeNode(9)),
                new TreeNode(6, new TreeNode(7), new TreeNode(5)));
        Assert.assertEquals(root, expect);
    }
}
